#include "Bsp.h"
#include "GraphicsDeviceManager.h"
#include "MatrixHelper.h"
#include "CameraManager.h"
#include "TextureManager.h"
#include "VertexBuffer.h"
#include "BoundingBoxRenderer.h"
#include "MathHelper.h"

#pragma warning (disable: 4482)

Bsp::Bsp()
{
	m_nVertexCount = 0;
	m_nFaceCount = 0;
	m_nIndexCount = 0;
	m_nTextureCount = 0;
	m_nLightmapCount = 0;
	m_nNodeCount = 0;
	m_nLeafCount = 0;
	m_nPlaneCount = 0;
	m_nBrushCount = 0;
	m_nBrushSideCount = 0;
	m_nLeafBrushCount = 0;
	m_nLeafFaceCount = 0;

	m_pVertexBuffer = NULL;
	m_pFaces = NULL;
	m_pIndexBuffer = NULL;
	m_pTextures = NULL;
	m_pNodes = NULL;
	m_pLeaves = NULL;
	m_pPlanes = NULL;
	m_pBrushes = NULL;
	m_pBrushSides = NULL;
	m_pLeafBrushes = NULL;
	m_pLeafFaces = NULL;
	m_pLastDiffuseTexture = NULL;
	m_nLastLightmapTexture = NULL;

	m_bCollided = false;
	m_traceRatio = 0;
	m_traceRadius = 0;
}

Bsp::~Bsp()
{
	Unload();
}

void Bsp::Load(std::string path)
{
	// TODO: Seperate distinct operations into seperate functions...maybe.
	FILE* file;

	fopen_s(&file, (path).c_str(), "rb");

	if(file == NULL)
	{
		assert(false);
	}

	BspHeader header;
	BspLump lumps[BSPLUMPS_COUNT];

	std::fread(&header, sizeof(BspHeader), 1, file);
	std::fread(&lumps, sizeof(BspLump), BSPLUMPS_COUNT, file);

	if(header.Magic != BSP_MAGIC || header.Version != BSP_VERSION)
	{
		assert(false);
	}
	
	// Entities
	char* entities = new char[lumps[BSPLUMPS_ENTITIES].Length];

	// TODO: Parse entities.

	std::fseek(file, lumps[BSPLUMPS_ENTITIES].Offset, SEEK_SET);
	std::fread(entities, sizeof(unsigned char), lumps[BSPLUMPS_ENTITIES].Length, file);

	// Vertices
	m_nVertexCount = lumps[BSPLUMPS_VERTICES].Length / sizeof(BspVertex);
	BspVertex* vertices0 = new BspVertex[m_nVertexCount];
	Vertex* vertices1 = new Vertex[m_nVertexCount];

	std::fseek(file, lumps[BSPLUMPS_VERTICES].Offset, SEEK_SET);
	std::fread(vertices0, sizeof(BspVertex), m_nVertexCount, file);

	for(int a = 0; a < m_nVertexCount; a++)
	{
		float z = -vertices0[a].Position.Y;

		vertices0[a].Position.Y = vertices0[a].Position.Z;
		vertices0[a].Position.Z = z;

		z = -vertices0[a].Normal.Y;

		vertices0[a].Normal.Y = vertices0[a].Normal.Z;
		vertices0[a].Normal.Z = z;
		
		//vertices1[a].Color = vertices0[a].Color;	// TODO
		vertices1[a].Position = vertices0[a].Position;
		vertices1[a].Normal = vertices0[a].Normal;
		vertices1[a].UV0 = vertices0[a].TextureCoordinate;
		vertices1[a].UV1 = vertices0[a].LightmapCoordinate;
	}

	m_pVertexBuffer = new VertexBuffer();
	m_pVertexBuffer->SetData(vertices1, sizeof(Vertex) * m_nVertexCount);

	delete[] vertices0;

	// Faces
	m_nFaceCount = lumps[BSPLUMPS_FACES].Length / sizeof(BspFace);
	m_pFaces = new BspFace[m_nFaceCount];

	std::fseek(file, lumps[BSPLUMPS_FACES].Offset, SEEK_SET);
	std::fread(m_pFaces, sizeof(BspFace), m_nFaceCount, file);

	for(int a = 0; a < m_nFaceCount; a++)
	{
		float z = -m_pFaces[a].Normal.Y;

		m_pFaces[a].Normal.Y = m_pFaces[a].Normal.Z;
		m_pFaces[a].Normal.Z = z;
	}

	// Indices
	m_nIndexCount = lumps[BSPLUMPS_INDICES].Length / sizeof(int);
	int* indices	= new int[m_nIndexCount];

	std::fseek(file, lumps[BSPLUMPS_INDICES].Offset, SEEK_SET);
	std::fread(indices, sizeof(int), m_nIndexCount, file);

	m_pIndexBuffer = new IndexBuffer();
	m_pIndexBuffer->SetData(indices, sizeof(int) * m_nIndexCount);

	m_pIndexBuffer = new IndexBuffer();
	m_pIndexBuffer->SetData(indices, sizeof(int) * m_nIndexCount);

	// Textures
	m_nTextureCount = lumps[BSPLUMPS_TEXTURES].Length / sizeof(BspTexture);
	m_pTextures = new BspTexture[m_nTextureCount];

	std::fseek(file, lumps[BSPLUMPS_TEXTURES].Offset, SEEK_SET);
	std::fread(m_pTextures, sizeof(BspTexture), m_nTextureCount, file);

	for(int a = 0; a < m_nTextureCount; a++)
	{
		// TODO: Fix the path to the files to use relative pathing.
		m_pTexture2Ds.push_back(TextureManager::Load("Content/" + std::string(m_pTextures[a].Name) + ".tga"));
	}

	// Nodes
	m_nNodeCount = lumps[BSPLUMPS_NODES].Length / sizeof(BspNode);
	m_pNodes = new BspNode[m_nNodeCount];

	std::fseek(file, lumps[BSPLUMPS_NODES].Offset, SEEK_SET);
	std::fread(m_pNodes, sizeof(BspNode), m_nNodeCount, file);

	for(int a = 0; a < m_nNodeCount; a++)
	{
		BspNode* node = &m_pNodes[a];

		// TODO: Convert bounding boxes.
	}

	// Leaves
	m_nLeafCount = lumps[BSPLUMPS_LEAVES].Length / sizeof(BspLeaf);
	m_pLeaves = new BspLeaf[m_nLeafCount];

	std::fseek(file, lumps[BSPLUMPS_LEAVES].Offset, SEEK_SET);
	std::fread(m_pLeaves, sizeof(BspLeaf), m_nLeafCount, file);

	for(int a = 0; a < m_nLeafCount; a++)
	{
		BspLeaf* leaf = &m_pLeaves[a];

		int temp = leaf->BoundingBox[1];

		leaf->BoundingBox[1] = leaf->BoundingBox[2];
		leaf->BoundingBox[2] = -temp;

		temp = leaf->BoundingBox[4];

		leaf->BoundingBox[4] = leaf->BoundingBox[5];
		leaf->BoundingBox[5] = -temp;
	}

	// Brushes
	m_nBrushCount = lumps[BSPLUMPS_BRUSHES].Length / sizeof(BspBrush);
	m_pBrushes = new BspBrush[m_nBrushCount];

	std::fseek(file, lumps[BSPLUMPS_BRUSHES].Offset, SEEK_SET);
	std::fread(m_pBrushes, sizeof(BspBrush), m_nBrushCount, file);

	// Brush sides
	m_nBrushSideCount = lumps[BSPLUMPS_BRUSHSIDES].Length / sizeof(BspBrushSide);
	m_pBrushSides = new BspBrushSide[m_nBrushSideCount];

	std::fseek(file, lumps[BSPLUMPS_BRUSHSIDES].Offset, SEEK_SET);
	std::fread(m_pBrushSides, sizeof(BspBrushSide), m_nBrushSideCount, file);

	// Planes
	m_nPlaneCount = lumps[BSPLUMPS_PLANES].Length / sizeof(BspPlane);
	m_pPlanes = new BspPlane[m_nPlaneCount];

	std::fseek(file, lumps[BSPLUMPS_PLANES].Offset, SEEK_SET);
	std::fread(m_pPlanes, sizeof(BspPlane), m_nPlaneCount, file);

	for(int a = 0; a < m_nPlaneCount; a++)
	{
		float z = -m_pPlanes[a].Normal.Y;

		m_pPlanes[a].Normal.Y = m_pPlanes[a].Normal.Z;
		m_pPlanes[a].Normal.Z = z;
	}

	// Leaf brushes
	m_nLeafBrushCount = lumps[BSPLUMPS_LEAFBRUSHES].Length / sizeof(int);
	m_pLeafBrushes = new int[m_nLeafBrushCount];

	std::fseek(file, lumps[BSPLUMPS_LEAFBRUSHES].Offset, SEEK_SET);
	std::fread(m_pLeafBrushes, sizeof(int), m_nLeafBrushCount, file);

	// Leaf faces
	m_nLeafFaceCount = lumps[BSPLUMPS_LEAFFACES].Length / sizeof(int);
	m_pLeafFaces = new int[m_nLeafFaceCount];

	std::fseek(file, lumps[BSPLUMPS_LEAFFACES].Offset, SEEK_SET);
	std::fread(m_pLeafFaces, sizeof(int), m_nLeafFaceCount, file);

	// Lightmaps
	m_nLightmapCount = lumps[BSPLUMPS_LIGHTMAPS].Length / sizeof(BspLightmap);
	BspLightmap* lightmaps = new BspLightmap[m_nLightmapCount];

	std::fseek(file, lumps[BSPLUMPS_LIGHTMAPS].Offset, SEEK_SET);
	std::fread(lightmaps, sizeof(BspLightmap), m_nLightmapCount, file);

	m_pLightmapTextureIndices = new unsigned int[m_nLightmapCount];

	for(int a = 0; a < m_nLightmapCount; a++)
	{
		CreateLightmapTexture(m_pLightmapTextureIndices[a], (unsigned char*)lightmaps[a].Bytes, 128, 128);

		// TODO: Adjust gamma.
	}

	delete[] lightmaps;

	std::fseek(file, lumps[BSPLUMPS_VISDATA].Offset, SEEK_SET);

	if(lumps[BSPLUMPS_VISDATA].Length != 0)
	{
		// Read in the number of vectors and each vector's size
		std::fread(&(m_oVisData.ClusterCount),	 1, sizeof(int), file);
		std::fread(&(m_oVisData.BytesPerCluster), 1, sizeof(int), file);

		// Allocate the memory for the cluster bitsets
		int size = m_oVisData.ClusterCount * m_oVisData.BytesPerCluster;

		m_oVisData.Bits = new byte[size];

		// Read in the all the visibility bitsets for each cluster
		std::fread(m_oVisData.Bits, 1, sizeof(byte) * size, file);
	}
	else
	{
		m_oVisData.Bits = NULL;
	}

	std::fclose(file);
}

void Bsp::Unload()
{
	m_nVertexCount = 0;
	m_nFaceCount = 0;
	m_nIndexCount = 0;
	m_nTextureCount = 0;
	m_nLightmapCount = 0;
	m_nNodeCount = 0;
	m_nLeafCount = 0;
	m_nPlaneCount = 0;
	m_nBrushCount = 0;
	m_nBrushSideCount = 0;
	m_nLeafBrushCount = 0;
	m_nLeafFaceCount = 0;

	//delete[] m_pVertices;
	delete		m_pVertexBuffer;
	delete[] m_pFaces;
	//delete[] m_pIndices;
	delete	 m_pIndexBuffer;
	delete[] m_pTextures;
	delete[] m_pNodes;
	delete[] m_pLeaves;
	delete[] m_pPlanes;
	delete[] m_pBrushes;
	delete[] m_pBrushSides;
	delete[] m_pLeafBrushes;
	delete[] m_pLeafFaces;

	//m_pVertices = NULL;
	m_pVertexBuffer = NULL;
	m_pFaces = NULL;
	//m_pIndices = NULL;
	m_pIndexBuffer = NULL;
	m_pTextures = NULL;
	m_pNodes = NULL;
	m_pLeaves = NULL;
	m_pPlanes = NULL;
	m_pBrushes = NULL;
	m_pBrushSides = NULL;
	m_pLeafBrushes = NULL;
	m_pLeafFaces = NULL;
}

void Bsp::Draw()
{
	m_nFacesDrawn.reset();

	Camera* camera = CameraManager::GetInstance()->GetCurrentCamera();

	int leafIndex = FindLeaf(camera->GetPosition());

	int cluster = m_pLeaves[leafIndex].Cluster;

	glEnable(GL_DEPTH_TEST);

	glActiveTextureARB(GL_TEXTURE0_ARB);
	glEnable(GL_TEXTURE_2D);

	glActiveTextureARB(GL_TEXTURE1_ARB);
	glEnable(GL_TEXTURE_2D);

	glEnableClientState(GL_VERTEX_ARRAY);
	glEnableClientState(GL_TEXTURE_COORD_ARRAY);

	glBindBufferARB(GL_ARRAY_BUFFER, m_pVertexBuffer->GetID());
	glBindBufferARB(GL_ELEMENT_ARRAY_BUFFER, m_pIndexBuffer->GetID());

	// TODO: Store a PVS (list of pointers to leaves that can be seen).
	// This will require lots of memory (approximately 2MB on a small map).
	for(int a = 0; a < m_nLeafCount; a++)
	{
		BspLeaf* leaf = &m_pLeaves[a];

		if(!IsClusterVisible(cluster, leaf->Cluster))
		{
			continue;
		}
		
		BoundingFrustum boundingFrustum = camera->GetBoundingFrustum();

		// TODO: This is slow!  We need a proper 'build' function so that we
		// store data types relevant to our math functions to avoid these
		// hideous cast operations thousands of times a draw call.
		BoundingBox boundingBox = BoundingBox(
			Vector3f((float)leaf->BoundingBox[0], (float)leaf->BoundingBox[1], (float)leaf->BoundingBox[2]),
			Vector3f((float)leaf->BoundingBox[3], (float)leaf->BoundingBox[4], (float)leaf->BoundingBox[5]));

		if(!boundingFrustum.Intersects(boundingBox))
		{
			continue;
		}

		int faceCount = leaf->FaceCount;

		while(faceCount--)
		{
			int faceIndex = m_pLeafFaces[leaf->FaceIndex + faceCount];

			if(m_nFacesDrawn[faceIndex])
			{
				continue;
			}
			
			BspFace* face = &m_pFaces[faceIndex];

			DrawFace(face);

			m_nFacesDrawn.set(faceIndex);
		}
	}

	glActiveTextureARB(GL_TEXTURE1_ARB);
	glBindTexture(GL_TEXTURE_2D, NULL);

	glActiveTextureARB(GL_TEXTURE0_ARB);
	glBindTexture(GL_TEXTURE_2D, NULL);

	glDisableClientState(GL_VERTEX_ARRAY);
	glDisableClientState(GL_TEXTURE_COORD_ARRAY);

	glBindBufferARB(GL_ELEMENT_ARRAY_BUFFER, 0);
	glBindBufferARB(GL_ARRAY_BUFFER, 0);
}

void Bsp::DrawFace(BspFace* face)
{
	// Position
	glVertexPointer(3, GL_FLOAT, sizeof(Vertex), BUFFER_OFFSET(face->StartVertexIndex * sizeof(Vertex)));

	// Normal
	glNormalPointer(GL_FLOAT, sizeof(Vertex), BUFFER_OFFSET(face->StartVertexIndex * sizeof(Vertex) + Vertex::NormalOffset));

	// Diffuse texture
	glActiveTextureARB(GL_TEXTURE0_ARB);
	glClientActiveTextureARB(GL_TEXTURE0_ARB);
	glTexCoordPointer(2, GL_FLOAT, sizeof(Vertex), BUFFER_OFFSET(face->StartVertexIndex * sizeof(Vertex) + Vertex::UV0Offset));
	glBindTexture(GL_TEXTURE_2D,  m_pTexture2Ds[face->TextureIndex]->GetID());

	// Lightmap texture
	glActiveTextureARB(GL_TEXTURE1_ARB);
	glClientActiveTextureARB(GL_TEXTURE1_ARB);
	glTexCoordPointer(2, GL_FLOAT, sizeof(Vertex), BUFFER_OFFSET(face->StartVertexIndex * sizeof(Vertex) + Vertex::UV1Offset));
	glBindTexture(GL_TEXTURE_2D, m_pLightmapTextureIndices[face->LightmapID]);

	glPolygonMode(GL_BACK, GL_FILL);
	glDrawElements(GL_TRIANGLES, face->IndexCount, GL_UNSIGNED_INT, BUFFER_OFFSET(face->StartIndex * sizeof(unsigned int)));
	
	//glActiveTextureARB(GL_TEXTURE0_ARB);
	//glClientActiveTextureARB(GL_TEXTURE0_ARB);
	//glBindTexture(GL_TEXTURE_2D, 0);

	glActiveTextureARB(GL_TEXTURE1_ARB);
	glClientActiveTextureARB(GL_TEXTURE1_ARB);
	glBindTexture(GL_TEXTURE_2D, 0);

	glPolygonMode(GL_BACK, GL_LINE);

	glDrawElements(GL_TRIANGLES, face->IndexCount, GL_UNSIGNED_INT, BUFFER_OFFSET(face->StartIndex * sizeof(unsigned int)));
}

const int Bsp::FindLeaf(const Vector3f &position) const
{
	int a = 0;
	float distance = 0.0f;

	while(a >= 0)
	{
		const BspNode& node = m_pNodes[a];
		const BspPlane& plane = m_pPlanes[node.PlaneIndex];

		distance = Vector3f::Dot(position, plane.Normal) - plane.Distance;

		if(distance >= 0)
		{
			a = node.Children[0];
		}
		else
		{
			a = node.Children[1];
		}
	}

	return ~a;
}

bool Bsp::IsClusterVisible(int current, int test)
{
	if(!m_oVisData.Bits || current < 0)
	{
		return 1;
	}

	// Use binary math to get the 8 bit visibility set for the current cluster
	unsigned char visSet = m_oVisData.Bits[(current * m_oVisData.BytesPerCluster) + (test >> 3)];
	
	// Now that we have our vector (bitset), do some bit shifting to find if
	// the "test" cluster is visible from the "current" cluster, according to the bitset.
	return (visSet & (1 << (test & 7))) != 0;
}

void Bsp::CreateLightmapTexture(unsigned int& id, unsigned char* bytes, int width, int height)
{
	glGenTextures(1, &id);
	glPixelStorei (GL_UNPACK_ALIGNMENT, 1);
	glBindTexture(GL_TEXTURE_2D, id);

	ChangeGamma(bytes, width * height * 3, 3.0f);

	gluBuild2DMipmaps(GL_TEXTURE_2D, 3, width, height, GL_RGB, GL_UNSIGNED_BYTE, bytes);
	glTexParameteri(GL_TEXTURE_2D,GL_TEXTURE_MAG_FILTER,GL_LINEAR);	
	glTexParameteri(GL_TEXTURE_2D, GL_TEXTURE_MIN_FILTER, GL_LINEAR_MIPMAP_NEAREST);
	glTexEnvf(GL_TEXTURE_ENV, GL_TEXTURE_ENV_MODE, GL_MODULATE);
}

void Bsp::ChangeGamma(unsigned char* bytes, int size, float factor)
{
	for(int i = 0; i < size / 3; i++, bytes += 3)
	{
		float scale = 1.0f, temp = 0.0f;
		float r = 0, g = 0, b = 0;

		// extract the current RGB values
		r = (float)bytes[0];
		g = (float)bytes[1];
		b = (float)bytes[2];

		// Multiply the factor by the RGB values, while keeping it to a 255 ratio
		r = r * factor / 255.0f;
		g = g * factor / 255.0f;
		b = b * factor / 255.0f;
		
		// Check if the the values went past the highest value
		if(r > 1.0f && (temp = (1.0f/r)) < scale) scale=temp;
		if(g > 1.0f && (temp = (1.0f/g)) < scale) scale=temp;
		if(b > 1.0f && (temp = (1.0f/b)) < scale) scale=temp;

		// Get the scale for this pixel and multiply it by our pixel values
		scale*=255.0f;		
		r*=scale;	g*=scale;	b*=scale;

		// Assign the new gamma'nized RGB values to our image
		bytes[0] = (byte)r;
		bytes[1] = (byte)g;
		bytes[2] = (byte)b;
	}
}

//void Bsp::Trace(Vector3f inputStart, Vector3f inputEnd)
//{
//	outputStartsOut = true;
//	outputAllSolid = false;
//	outputFraction = 1.0f;
//
//	TraceNode(0, 0.0f, 1.0f, inputStart, inputEnd);
//
//	if (outputFraction == 1.0f)
//	{
//		outputEnd = inputEnd;
//	}
//	else
//	{
//		outputEnd = inputStart + ((inputEnd - inputStart) * outputFraction);
//	}
//}
//
//void Bsp::TraceNode(int nodeIndex, float startFraction, float endFraction, Vector3f start, Vector3f end)
//{
//	if (nodeIndex < 0)
//	{
//		BspLeaf *leaf = &m_pLeaves[-(nodeIndex + 1)];
//
//		for (int i = 0; i < leaf->BrushCount; i++)
//		{
//			BspBrush *brush = &m_pBrushes[m_pLeafBrushes[leaf->BrushIndex + i]];
//
//			if (brush->BrushSideCount > 0 && m_pTextures[brush->TextureIndex].Type & 1)
//			{
//				TraceBrush(brush, start, end);
//			}
//		}
//
//		return;
//	}
//
//	BspNode *node = &m_pNodes[nodeIndex];
//	BspPlane *plane = &m_pPlanes[node->Plane];
//
//	float startDistance = Vector3f::Dot(start, plane->Normal) - plane->Distance;
//	float endDistance = Vector3f::Dot(end, plane->Normal) - plane->Distance;
//
//	if (startDistance >= 0 && endDistance >= 0)
//	{
//		TraceNode(node->Children[0], startDistance, endDistance, start, end);
//	}
//	else if (startDistance < 0 && endDistance < 0)
//	{
//		TraceNode(node->Children[1], startDistance, endDistance, start, end);
//	}
//	else
//	{
//		int side = node->Children[0];
//		float fraction1, fraction2, middleFraction;
//		Vector3f middle;
//
//		if (startDistance < endDistance)
//		{
//			side = node->Children[1];
//			float inverseDistance = 1.0f / (startDistance - endDistance);
//			fraction1 = (startDistance - BSP_EPSILON) * inverseDistance;
//			fraction2 = (startDistance + BSP_EPSILON) * inverseDistance;
//		}
//		else if (endDistance < startDistance)
//		{
//			side = node->Children[0];
//			float inverseDistance = 1.0f / (startDistance - endDistance);
//			fraction1 = (startDistance + BSP_EPSILON) * inverseDistance;
//			fraction2 = (startDistance - BSP_EPSILON) * inverseDistance;
//		}
//		//else
//		//{
//		//	side = node->Children[0];
//		//	fraction1 = 1.0f;
//		//	fraction2 = 0.0f;
//		//}
//
//		Clamp(fraction1, 0, 1);
//		Clamp(fraction2, 0, 1);
//
//		middleFraction = startFraction + ((endFraction - startFraction) * fraction1);
//		middle = start + ((end - start) * fraction1);
//
//		TraceNode(side, startFraction, middleFraction, start, middle);
//
//		middleFraction = startFraction + ((endFraction - startFraction) * fraction2);
//		middle = start + ((end - start) * fraction2);
//
//		if(side == node->Children[1])
//			TraceNode(node->Children[0], middleFraction, endFraction, middle, end);
//		else
//			TraceNode(node->Children[1], middleFraction, endFraction, middle, end);
//	}
//}
//
//void Bsp::TraceBrush(BspBrush *brush, Vector3f inputStart, Vector3f inputEnd)
//{
//	float startFraction = -1.0f;
//	float endFraction = 1.0f;
//	boolean startsOut = false;
//	boolean endsOut = false;
//
//	for (int i = 0; i < brush->BrushSideCount; i++)
//	{
//		BspBrushSide *brushSide = &m_pBrushSides[brush->BrushSideIndex + i];
//		BspPlane *plane = &m_pPlanes[brushSide->PlaneIndex];
//
//		float startDistance = Vector3f::Dot(inputStart, plane->Normal) - plane->Distance;
//		float endDistance = Vector3f::Dot(inputEnd, plane->Normal) - plane->Distance;
//
//		if (startDistance > 0)
//		{
//			startsOut = true;
//		}
//
//		if (startDistance > 0 && endDistance > 0)
//		{
//			return;
//		}
//
//		if (startDistance <= 0 && endDistance <= 0)
//		{
//			continue;
//		}
//
//		//if (endDistance > 0)
//		//{
//		//	endsOut = true;
//		//}
//
//		if (startDistance > endDistance)
//		{
//			float fraction = (startDistance - BSP_EPSILON) / (startDistance - endDistance);
//
//			if (fraction > startFraction)
//			{
//				startFraction = fraction;
//			}
//		}
//		else
//		{
//			float fraction = (startDistance + BSP_EPSILON) / (startDistance - endDistance);
//
//			if (fraction < endFraction)
//			{
//				endFraction = fraction;
//			}
//		}
//	}
//
//	if (!startsOut)
//	{
//		outputStartsOut = false;
//
//		if (!endsOut)
//		{
//			outputAllSolid = true;
//		}
//
//		return;
//	}
//
//	if (startFraction < endFraction)
//	{
//		if (startFraction > -1 && startFraction < outputFraction)
//		{
//			if (startFraction < 0)
//			{
//				startFraction = 0;
//			}
//
//			outputFraction = startFraction;
//		}
//	}
//}

Vector3f Bsp::Trace(Vector3f vStart, Vector3f vEnd)
{
	// Initially we set our trace ratio to 1.0f, which means that we don't have
	// a collision or intersection point, so we can move freely.
	m_traceRatio = 1.0f;
	
	// We start out with the first node (0), setting our start and end ratio to 0 and 1.
	// We will recursively go through all of the nodes to see which brushes we should check.
	CheckNode(0, 0.0f, 1.0f, vStart, vEnd);

	// If the traceRatio is STILL 1.0f, then we never collided and just return our end position
	if(m_traceRatio == 1.0f)
	{
		return vEnd;
	}
	else	// Else COLLISION!!!!
	{
		// If we get here then it's assumed that we collided and need to move the position
		// the correct distance from the starting position a position around the intersection
		// point.  This is done by the cool equation below (described in detail at top of page).

		// Set our new position to a position that is right up to the brush we collided with
		Vector3f vNewPosition = vStart + ((vEnd - vStart) * m_traceRatio);

		// Return the new position to be used by our camera (or player)
		return vNewPosition;
	}
}


/////////////////////////////////// TRACE RAY \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*
/////
/////	This takes a start and end position (ray) to test against the BSP brushes
/////
/////////////////////////////////// TRACE RAY \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*

Vector3f Bsp::TraceRay(Vector3f vStart, Vector3f vEnd)
{
	// We don't use this function, but we set it up to allow us to just check a
	// ray with the BSP tree brushes.  We do so by setting the trace type to TYPE_RAY.
	m_traceType = TYPE_RAY;

	// Run the normal Trace() function with our start and end 
	// position and return a new position
	return Trace(vStart, vEnd);
}


/////////////////////////////////// TRACE SPHERE \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*
/////
/////	This tests a sphere around our movement vector against the BSP brushes for collision
/////
/////////////////////////////////// TRACE SPHERE \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*

Vector3f Bsp::TraceSphere(Vector3f vStart, Vector3f vEnd, float radius)
{
	// In this tutorial we are doing sphere collision, so this is the function
	// that we will be doing to initiate our collision checks.

	// Here we initialize the type of trace (SPHERE) and initialize other data
	m_traceType = TYPE_SPHERE;
	m_bCollided = false;
	m_traceRadius = radius;

	// Get the new position that we will return to the camera or player
	Vector3f vNewPosition = Trace(vStart, vEnd);

	// Return the new position to be changed for the camera or player
	return vNewPosition;
}


/////////////////////////////////// CHECK NODE \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*
/////
/////	This traverses the BSP to find the brushes closest to our position
/////
/////////////////////////////////// CHECK NODE \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*

void Bsp::CheckNode(int nodeIndex, float startRatio, float endRatio, Vector3f vStart, Vector3f vEnd)
{
	// Remember, the nodeIndices are stored as negative numbers when we get to a leaf, so we 
	// check if the current node is a leaf, which holds brushes.  If the nodeIndex is negative,
	// the next index is a leaf (note the: nodeIndex + 1)
	if(nodeIndex < 0)
	{
		// If this node in the BSP is a leaf, we need to negate and add 1 to offset
		// the real node index into the m_pLeafs[] array.  You could also do [~nodeIndex].
		BspLeaf *pLeaf = &m_pLeaves[-(nodeIndex + 1)];

		// We have a leaf, so let's go through all of the brushes for that leaf
		for(int i = 0; i < pLeaf->BrushCount; i++)
		{
			// Get the current brush that we going to check
			BspBrush *pBrush = &m_pBrushes[m_pLeafBrushes[pLeaf->BrushIndex + i]];

			// This is kind of an important line.  First, we check if there is actually
			// and brush sides (which store indices to the normal and plane data for the brush).
			// If not, then go to the next one.  Otherwise, we also check to see if the brush
			// is something that we want to collide with.  For instance, there are brushes for
			// water, lava, bushes, misc. sprites, etc...  We don't want to collide with water
			// and other things like bushes, so we check the texture type to see if it's a solid.
			// If the textureType can be binary-anded (&) and still be 1, then it's solid,
			// otherwise it's something that can be walked through.  That's how Quake chose to
			// do it.

			// Check if we have brush sides and the current brush is solid and collidable
			if((pBrush->BrushSideCount > 0) && (m_pTextures[pBrush->TextureIndex].Type & 1))
			{
				// Now we delve into the dark depths of the real calculations for collision.
				// We can now check the movement vector against our brush planes.
				CheckBrush(pBrush, vStart, vEnd);
			}
		}

		// Since we found the brushes, we can go back up and stop recursing at this level
		return;
	}

	// If we haven't found a leaf in the node, then we need to keep doing some dirty work
	// until we find the leafs which store the brush information for collision detection.

	// Grad the next node to work with and grab this node's plane data
	BspNode *pNode = &m_pNodes[nodeIndex];
	BspPlane *pPlane = &m_pPlanes[pNode->PlaneIndex];
	
	// Now we do some quick tests to see which side we fall on of the node in the BSP

	// Here we use the plane equation to find out where our initial start position is
	// according the the node that we are checking.  We then grab the same info for the end pos.
	float startDistance = Vector3f::Dot(vStart, pPlane->Normal) - pPlane->Distance;
	float endDistance = Vector3f::Dot(vEnd, pPlane->Normal) - pPlane->Distance;
	float offset = 0.0f;

	// If we are doing any type of collision detection besides a ray, we need to change
	// the offset for which we are testing collision against the brushes.  If we are testing
	// a sphere against the brushes, we need to add the sphere's offset when we do the plane
	// equation for testing our movement vector (start and end position).  * More Info * For
	// more info on sphere collision, check out our tutorials on this subject.

	// If we are doing sphere collision, include an offset for our collision tests below
	if(m_traceType == TYPE_SPHERE)
		offset = m_traceRadius;

	// Below we just do a basic traversal down the BSP tree.  If the points are in
	// front of the current splitter plane, then only check the nodes in front of
	// that splitter plane.  Otherwise, if both are behind, check the nodes that are
	// behind the current splitter plane.  The next case is that the movement vector
	// is on both sides of the splitter plane, which makes it a bit more tricky because we now
	// need to check both the front and the back and split up the movement vector for both sides.

	// Here we check to see if the start and end point are both in front of the current node.
	// If so, we want to check all of the nodes in front of this current splitter plane.
	if(startDistance >= offset && endDistance >= offset)
	{
		// Traverse the BSP tree on all the nodes in front of this current splitter plane
		CheckNode(pNode->Children[0], startDistance, endDistance, vStart, vEnd);
	}
	// If both points are behind the current splitter plane, traverse down the back nodes
	else if(startDistance < -offset && endDistance < -offset)
	{
		// Traverse the BSP tree on all the nodes in back of this current splitter plane
		CheckNode(pNode->Children[1], startDistance, endDistance, vStart, vEnd);
	}	
	else
	{
		// If we get here, then our ray needs to be split in half to check the nodes
		// on both sides of the current splitter plane.  Thus we create 2 ratios.
		float Ratio1 = 1.0f, Ratio2 = 0.0f, middleRatio = 0.0f;
		Vector3f vMiddle;	// This stores the middle point for our split ray

		// Start of the side as the front side to check
		int side = pNode->Children[0];

		// Here we check to see if the start point is in back of the plane (negative)
		if(startDistance < endDistance)
		{
			// Since the start position is in back, let's check the back nodes
			side = pNode->Children[1];

			// Here we create 2 ratios that hold a distance from the start to the
			// extent closest to the start (take into account a sphere and epsilon).
			// We use epsilon like Quake does to compensate for float errors.  The second
			// ratio holds a distance from the other size of the extents on the other side
			// of the plane.  This essential splits the ray for both sides of the splitter plane.
			float inverseDistance = 1.0f / (startDistance - endDistance);
			Ratio1 = (startDistance - offset - BSP_EPSILON) * inverseDistance;
			Ratio2 = (startDistance + offset + BSP_EPSILON) * inverseDistance;
		}
		// Check if the starting point is greater than the end point (positive)
		else if(startDistance > endDistance)
		{
			// This means that we are going to recurse down the front nodes first.
			// We do the same thing as above and get 2 ratios for split ray.
			// Ratio 1 and 2 are switched in contrast to the last if statement.
			// This is because the start is starting in the front of the splitter plane.
			float inverseDistance = 1.0f / (startDistance - endDistance);
			Ratio1 = (startDistance + offset + BSP_EPSILON) * inverseDistance;
			Ratio2 = (startDistance - offset - BSP_EPSILON) * inverseDistance;
		}

		// Make sure that we have valid numbers and not some weird float problems.
		// This ensures that we have a value from 0 to 1 as a good ratio should be :)
		if (Ratio1 < 0.0f) Ratio1 = 0.0f;
        else if (Ratio1 > 1.0f) Ratio1 = 1.0f;

        if (Ratio2 < 0.0f) Ratio2 = 0.0f;
        else if (Ratio2 > 1.0f) Ratio2 = 1.0f;

		// Just like we do in the Trace() function, we find the desired middle
		// point on the ray, but instead of a point we get a middleRatio percentage.
		// This isn't the true middle point since we are using offset's and the epsilon value.
		// We also grab the middle point to go with the ratio.
		middleRatio = startRatio + ((endRatio - startRatio) * Ratio1);
		vMiddle = vStart + ((vEnd - vStart) * Ratio1);

		// Now we recurse on the current side with only the first half of the ray
		CheckNode(side, startRatio, middleRatio, vStart, vMiddle);

		// Now we need to make a middle point and ratio for the other side of the node
		middleRatio = startRatio + ((endRatio - startRatio) * Ratio2);
		vMiddle = vStart + ((vEnd - vStart) * Ratio2);

		// Depending on which side should go last, traverse the bsp with the
		// other side of the split ray (movement vector).
		if(side == pNode->Children[1])
			CheckNode(pNode->Children[0], middleRatio, endRatio, vMiddle, vEnd);
		else
			CheckNode(pNode->Children[1], middleRatio, endRatio, vMiddle, vEnd);
	}
}


/////////////////////////////////// CHECK BRUSH \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*
/////
/////	This checks our movement vector against all the planes of the brush
/////
/////////////////////////////////// CHECK BRUSH \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*

void Bsp::CheckBrush(BspBrush *pBrush, Vector3f vStart, Vector3f vEnd)
{
	float startRatio = -1.0f;		// Like in BrushCollision.htm, start a ratio at -1
    float endRatio = 1.0f;			// Set the end ratio to 1
    bool startsOut = false;			// This tells us if we starting outside the brush

	// This function actually does the collision detection between our movement
	// vector and the brushes in the world data.  We will go through all of the
	// brush sides and check our start and end ratio against the planes to see if
	// they pass each other.  We start the startRatio at -1 and the endRatio at
	// 1, but as we set the ratios to their intersection points (ratios), then
	// they slowly move toward each other.  If they pass each other, then there
	// is definitely not a collision.

	// Go through all of the brush sides and check collision against each plane
	for(int i = 0; i < pBrush->BrushSideCount; i++)
	{
		// Here we grab the current brush side and plane in this brush
		BspBrushSide *pBrushSide = &m_pBrushSides[pBrush->BrushSideIndex + i];
		BspPlane *pPlane = &m_pPlanes[pBrushSide->PlaneIndex];

		// Let's store a variable for the offset (like for sphere collision)
		float offset = 0.0f;

		// If we are testing sphere collision we need to add the sphere radius
		if(m_traceType == TYPE_SPHERE)
			offset = m_traceRadius;

		// Test the start and end points against the current plane of the brush side.
		// Notice that we add an offset to the distance from the origin, which makes
		// our sphere collision work.
		float startDistance = Vector3f::Dot(vStart, pPlane->Normal) - (pPlane->Distance + offset);
		float endDistance = Vector3f::Dot(vEnd, pPlane->Normal) - (pPlane->Distance + offset);

		// Make sure we start outside of the brush's volume
		if(startDistance > 0)	startsOut = true;

		// Stop checking since both the start and end position are in front of the plane
		if(startDistance > 0 && endDistance > 0)
			return;

		// Continue on to the next brush side if both points are behind or on the plane
		if(startDistance <= 0 && endDistance <= 0)
			continue;

		// If the distance of the start point is greater than the end point, we have a collision!
		if(startDistance > endDistance)
		{
			// This gets a ratio from our starting point to the approximate collision spot
			float Ratio1 = (startDistance - BSP_EPSILON) / (startDistance - endDistance);

			// If this is the first time coming here, then this will always be true,
			// since startRatio starts at -1.0f.  We want to find the closest collision,
			// so we still continue to check all of the brushes before quitting.
			if(Ratio1 > startRatio)
			{
				// Set the startRatio (currently the closest collision distance from start)
				startRatio = Ratio1;
				m_bCollided = true;		// Let us know we collided!
			}
		}
		else
		{
			// Get the ratio of the current brush side for the endRatio
			float Ratio = (startDistance + BSP_EPSILON) / (startDistance - endDistance);

			// If the ratio is less than the current endRatio, assign a new endRatio.
			// This will usually always be true when starting out.
			if(Ratio < endRatio)
				endRatio = Ratio;
		}
	}

	// If we didn't start outside of the brush we don't want to count this collision - return;
	if(startsOut == false)
	{
		return;
	}
	
	// If our startRatio is less than the endRatio there was a collision!!!
	if(startRatio < endRatio)
	{
		// Make sure the startRatio moved from the start and check if the collision
		// ratio we just got is less than the current ratio stored in m_traceRatio.
		// We want the closest collision to our original starting position.
		if(startRatio > -1 && startRatio < m_traceRatio)
		{
			// If the startRatio is less than 0, just set it to 0
			if(startRatio < 0)
				startRatio = 0;

			// Store the new ratio in our member variable for later
			m_traceRatio = startRatio;
		}
	}
}